/**
 * https://leetcode-cn.com/problems/symmetric-tree/
 * 对称二叉树
 * @param root 
 */
const isSymmetric = (root: TreeNode | null): boolean => {
    // 边界判断
    if (root === null) return true;

    // 判断是不是同一颗树
    const check = (p: TreeNode | null, q: TreeNode | null): boolean => {
        // p或者q为空
        if (p === null || q === null) return p === q

        // 使用中序遍历
        const pArr: TreeNode[] = [],
            qArr: TreeNode[] = [];

        pArr.push(p);
        qArr.push(q)
        while (pArr.length && qArr.length) {
            const n1 = pArr.pop()!
            const n2 = qArr.pop()!


            // 只要又不相同的, 返回false
            if (n1.val !== n2.val) return false


            // 左边
            if (n1.left !== null && n2.right !== null) {
                pArr.push(n1.left)
                qArr.push(n2.right)
            } else if ((n1.left === null && n2.right !== null) || (n1.left !== null && n2.right == null)) {
                return false
            }

            // 右边
            if (n1.right !== null && n2.left !== null) {
                pArr.push(n1.right)
                qArr.push(n2.left)
            } else if ((n1.right === null && n2.left !== null) || (n1.right !== null && n2.left == null)) {
                return false
            }
        }

        return true;
    };

    return check(root, root)
};



const isSymmetric3 = (root: TreeNode | null): boolean => {
    // 边界判断
    if (root === null) return true;

    // 翻转二叉树
    const reverse = (p: TreeNode | null) => {
        if (p === null) return;
        const tmp = p.left;
        p.left = p.right;
        p.right = tmp

        // 翻转左子树
        if (p.left !== null) {
            reverse(p.left)
        }

        // 翻转右子树
        if (p.right !== null) {
            reverse(p.right)
        }
    }


    // 判断是不是同一颗树
    const isSameTree = (p: TreeNode | null, q: TreeNode | null): boolean => {
        // p或者q为空
        if (p === null || q === null) return p === q

        // 使用中序遍历
        const pArr: TreeNode[] = [],
            qArr: TreeNode[] = [];

        let l = p,
            r = q;
        pArr.push(l);
        qArr.push(r)
        while (pArr.length && qArr.length) {
            const n1 = pArr.pop()!
            const n2 = qArr.pop()!

            // 只要又不相同的, 返回false
            if (n1.val !== n2.val) return false

            // 左边的树
            if (n1.left !== null && n2.left !== null) {
                pArr.push(n1.left)
                qArr.push(n2.left)
            } else if ((n1.left === null && n2.left !== null) || (n1.left !== null && n2.left == null)) {
                // 有一边为空, 另一边不为空
                return false
            }


            // 右边的树
            if (n1.right !== null && n2.right !== null) {
                pArr.push(n1.right)
                qArr.push(n2.right)
            } else if ((n1.right === null && n2.right !== null) || (n1.right !== null && n2.right == null)) {
                // 有一边为空, 另一边不为空
                return false
            }
        }

        return true;
    };

    // 将右子树翻转
    reverse(root.right)


    return isSameTree(root.left, root.right)
};

// 翻转二叉树 + 递归
const isSymmetric2 = (root: TreeNode | null): boolean => {
    // 边界判断
    if (root === null) return true;

    // 翻转二叉树
    const reverse = (p: TreeNode | null) => {
        if (p === null) return;
        const tmp = p.left;
        p.left = p.right;
        p.right = tmp

        // 翻转左子树
        if (p.left !== null) {
            reverse(p.left)
        }

        // 翻转右子树
        if (p.right !== null) {
            reverse(p.right)
        }
    }


    // 判断是不是同一颗树
    const isSameTree = (p: TreeNode | null, q: TreeNode | null): boolean => {
        // p或者q为null的情况
        if (p === null || q === null) return q === p

        if (p.val !== q.val) return false

        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }

    // 将右子树翻转
    reverse(root.right)


    return isSameTree(root.left, root.right)
};